package _11_整理题目._4_动态规划._子数组子矩阵;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/maximum-sum-circular-subarray/
 * https://leetcode-cn.com/problems/maximum-sum-circular-subarray/solution/wo-hua-yi-bian-jiu-kan-dong-de-ti-jie-ni-892u/
 *
 * 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和。
 *
 * 环形数组 意味着数组的末端将会与开头相连呈环状。形式上，
 * nums[i] 的下一个元素是 nums[(i + 1) % n] ，
 * nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
 *
 * 分类讨论：
 *      当最大子数组在内部，计算同 连续子数组最大和 一样
 *      当最大子数组在收尾，那么反向 最小子数组和一定在内部，可用 total 减去
 *      （一种边界，如果最小子数组和是所有的，全是负数，则 不返回 total 减去 min）
 *      最终比较两种情况的 最大值 即为解
 */
public class _02_环形子数组的最大和 {

    // 新建 dp，时间 O(n)，空间 O(n)
    public int maxSubCircular1(int[] nums) {
        int n = nums.length;
        int total = Arrays.stream(nums).sum();
        int[] dpMin = Arrays.copyOf(nums, n);
        int[] dpMax = Arrays.copyOf(nums, n);
        int max = nums[0], min = nums[0];
        for (int i = 1; i < n; i++) {
            dpMin[i] = Math.min(dpMin[i-1]+nums[i], nums[i]);
            min = Math.min(min, dpMin[i]);
            dpMax[i] = Math.max(dpMax[i-1]+nums[i], nums[i]);
            max = Math.max(max, dpMax[i]);
        }
        if (min == total) {
            return max;
        } else {
            return Math.max(max, total-min);
        }
    }

    @Test
    public void main() {
        int[] nums = {5,-3,5}; // 10
        int[] nums1 = {-3,-2,-3}; // -2
        System.out.println(maxSubCircular1(nums));
        System.out.println(maxSubCircular1(nums1));
    }

}
